/*
 *  Insertion Sort
 *
 *  Description:
 *  The cost of compare and swap depend on the number of inverions
 *
 *  Promotion tips:
 *  1. put smallest element in position to serve as sentinel
 *  2. binary insertion
 */

package algs4.sort;

import java.util.Random;

public class Insertion
{
    public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            int j;
            Comparable v = a[i];
            for (j = i; j > 0 && v.compareTo(a[j-1]) < 0; j--)
                a[j] = a[j-1];
            a[j] = v;
        }
    }

    private static void show(Comparable[] a) {
        for (Comparable i : a)
            System.out.print(i + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.out.println("Usage: Command N");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);;

        // Build random array of integer
        Integer[] a   = new Integer[n];
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < n; i++)
            a[i] = random.nextInt(n);

        System.out.print("BF: "); show(a);
        sort(a);
        System.out.print("AF: "); show(a);
    }
}
